A commercial printing firm is trying to determine the best mix of printing jobs it should seek, given its current capacity constraints in its four capital-intensive departments: typesetting, camera, pressroom, and bindery. It has classified its commercial work into three classes: A, B, and C, each requiring different amounts of time in the four major departments.
The production requirements in hours per unit of product are as follows:
Class A | Class B | Class C | |
---|---|---|---|
Typesetting | 0 | 2 | 3 |
Camera | 3 | 1 | 3 |
Pressroom | 3 | 6 | 2 |
Bindery | 5 | 4 | 0 |
Assuming these units of work are produced using regular time, the contribution to overhead and profit is \$200 for each unit of Class A work, \$300 for each unit of Class B work, and \$100 for each unit of Class C work.
The firm currently has the following regular-time capacity available in each department for the next time period: typesetting, 40 hours; camera, 60 hours; pressroom, 200 hours; bindery, 160 hours. In addition to this regular time, the firm could utilize an overtime shift in typesetting, which would make available an additional 35 hours in that department. The premium for this overtime (i.e., incremental costs in addition to regular time) would be \$4/hour.
Since the firm wants to find the optimal job mix for its equipment, management assumes it can sell all it produces. However, to satisfy long-established customers, management decides to produce at least 10 units of each class A,B, and at least 5 units of class C of work in each time period.
Assuming that the firm wants to maximize its contribution to profit and overhead, we can formulate the above situation as a linear program, as follows:
$X_{AR}$ = Number of units of Class A work produced on regular time
$X_{BR}$ = Number of units of Class B work produced on regular time
$X_{CR}$ = Number of units of Class C work produced on regular time
$X_{BO}$ = Number of units of Class B work produced on overtime typesetting
$X_{CO}$ = Number of units of Class C work produced on overtime typesetting
In [10]:
using JuMP
m = Model()
# Definig variable
Classes = ["A", "B", "C"]
Shift = ["R", "O"]
@variable(m, x[Classes, Shift] >= 0)
# Define Constraints
@constraints m begin
2x["B","R"] + 3x["C","R"] <= 40
2x["B","O"] + 3x["C","O"] <= 35
3x["A","R"] + x["B","R"] + 3x["C","R"] + x["B","O"] + 3x["C","O"] <= 60
3x["A","R"] + 6x["B","R"] + 2x["C","R"] + 6x["B","O"] + 2x["C","O"] <= 200
5x["A","R"] + 4x["B","R"] + 4x["B","O"] <= 160
x["A","R"] >= 10
x["B","R"] + x["B","O"] >= 10
x["C","R"] + x["C","O"] >= 5
end
@objective(m, Max, 200x["A","R"] + 300x["B","R"] + 100x["C","R"] + 292x["B","O"] + 88x["C","O"])
print(m)
In [11]:
solve(m)
println("Optimal Profit: ", getobjectivevalue(m))
println(getvalue(x))
In [12]:
writeLP(m, "printing.lp")
In [1]:
!less printing.lp
In [2]:
!glpsol --cpxlp printing.lp --ranges printing.sen
In [3]:
!less printing.sen
Is there a unique optimum solution for the LP?
No. There are three items in the sensitivity report that lead to this conclusion. First of all, consider the allowable increase in the profit coefficient of BO. In an optimal solution BO = 0. The sensitivity report (SR) says that the optimal solution will change if the profit coefficient of BO increases by more than 0. This means that if the unit profit of BO increases from 292 to 293 +ϵ, the optimal solution will change, even if ϵ is arbitrarily close to 0. This could only occur if there is an alternative optimal solution in which BO is strictly greater than 0. A second item in the sensitivity report that implies multiple optimal solutions is the allowable decrease of the profit coefficient of BR, which is 0. This means that if the profit coefficient decreases from 300 to 300−ϵ, the optimal solution will change. This could only occur if there is an alternative optimal solution in which BR is less than 15 (its value in the current optimal solution.) There is one more item that implies that there are alternative optimal solutions, the reduced cost of BO. In an optimal solution BO = 0, and its reduced cost is 0. This means that if we were to add a constraint requiring that BO ≥ϵ, where ϵ is positive and very close to 0, the change in the optimal objective value would be 0. This can only happen if there is an alternative optimal solution in which BO is strictly positive. And we can be sure that to be able to choose a value of ϵ that is strictly positive because of the 100% rule used in conjunction with pricing out BO. (We leave that exercise to the readers. There is a concept in linear programming known as "degeneracy." If a linear programming solution is degenerate, it could possibly mess up the conclusion based on the first two arguments above, but it would not invalidate the 3rd argument. In fact, the optimal solution of the SR can be shown to be non-degenerate. But if degeneracy was a concern to you, you know much more about linear programming than we are teaching you in this course.
If the printing firm has a chance to sell a new type of work that requires 0 hours of typesetting, 2 hours of camera, 2 hours of pressroom, and 1 hour of bindery, what contribution is required to make it attractive?
Answer: Only overtime camera is consumed completely, other resource are already avilable. Cost of overtime camera in per unit production of new product = 2 x (Shdadow Price) = 2 x 292 = 584.